package com.ruima.study.arithmetic.sortdemo.practice;

/**
 * <p>
 * <p>求逆序对</p>
 * <p>
 * <p>Copyright (c) 2024/11/16 15:24, 科大讯飞 All Rights Reserve</p>
 *
 * @author ruima6
 * @version [V1.0]
 */
public class LastDemo {

    public static void main(String[] args) {
        int[] arr = {9,7,5,4,6};
        long inversions = calNxCount(arr,0, arr.length - 1);
        System.out.println("Number of inversions: " + inversions);
    }

    public static int calNxCount(int[] arr,int start,int end){
        int count = 0;
        if (start >= end){
            return 0;
        }
        int mid = (start + end) / 2;
        count += calNxCount(arr, start, mid);
        count += calNxCount(arr, mid + 1, end);
        count += merge(arr, start, mid, end);
        return count;
    }


    public static int merge(int[] arr,int start,int end,int size){
        int count = 0;
        int k = 0;
        int i = start;
        int j = end + 1;

        while (i <= end && j <= size){
            if (arr[i] <= arr[j]){
                arr[k++] = arr[i];
                i++;
            }else{
                arr[k++] = arr[j];
                count += end - i + 1;
                j++;
            }
        }

        while (i <= end){
            arr[k++] = arr[i];
            i++;
        }
        while (j <= size){
            arr[k++] = arr[j];
            j++;
        }

        for (int l = 0; l < arr.length; ++l) {
            arr[start + l] = arr[l++];
        }
        return count;
    }

}
